package class1;

import java.util.Arrays;

/**
 * 归并排序
 * <p>
 * temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]
 * 这部分是将两个已排序的子数组中的较小元素放入 temp 数组的当前空位，具体步骤如下：
 * arr[p1] <= arr[p2]：这部分是判断左子数组当前元素 arr[p1] 是否小于或等于右子数组当前元素 arr[p2]。
 * <p>
 * 如果 arr[p1] <= arr[p2] 为 true，则说明左子数组当前元素较小，我们就将左子数组的当前元素放入 temp[i] 中，并且将 p1 向右移动一位（即 p1++）。
 * 如果 arr[p1] <= arr[p2] 为 false，则说明右子数组当前元素较小，我们将右子数组的当前元素放入 temp[i] 中，并且将 p2 向右移动一位（即 p2++）。
 * temp[i++]：将较小的元素放入临时数组 temp 的当前位置，并且递增 i，准备填入下一个位置。i++ 是后缀自增，意味着先将 temp[i] 赋值，然后再让 i 增加 1。
 * <p>
 * 总结：
 * 如果左子数组的元素小于等于右子数组的元素，将左子数组的元素放入 temp，并将 p1 向右移动。
 * 如果右子数组的元素小于左子数组的元素，将右子数组的元素放入 temp，并将 p2 向右移动。
 */
public class Code08_MergeSort {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 5, 1, 9, 12, 6, 7, 3, 1};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void mergeSort(int[] arr) {
        process(arr, 0, arr.length - 1);
    }

    public static void process(int[] arr, int L, int R) {
        if (L == R) {
            return;  // 基本情况，数组只含有一个元素
        }
        int mid = L + ((R - L) >> 1);  // 计算中间位置
        process(arr, L, mid);  // 递归排序左半部分
        process(arr, mid + 1, R);  // 递归排序右半部分
        merge(arr, L, mid, R);  // 合并左右两部分
    }

    public static void merge(int[] arr, int L, int mid, int R) {
        int[] temp = new int[R - L + 1];  // 创建临时数组，存储合并后的结果
        int i = 0;
        int p1 = L;  // 左子数组的起始位置
        int p2 = mid + 1;  // 右子数组的起始位置

        // 合并两个已排序的子数组
        while (p1 <= mid && p2 <= R) {
            temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }

        // 如果左子数组还有剩余元素
        while (p1 <= mid) {
            temp[i++] = arr[p1++];
        }

        // 如果右子数组还有剩余元素
        while (p2 <= R) {
            temp[i++] = arr[p2++];
        }
        System.out.println(Arrays.toString(temp));

        // 将合并后的临时数组复制回原数组
        for (i = 0; i < temp.length; i++) {
            arr[i + L] = temp[i];
        }
        System.out.println(Arrays.toString(arr));


    }

}
